|
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them. One speaks of the circuit complexity of a Boolean circuit. A related notion is the circuit complexity of a recursive language that is decided by a family of circuits (see below). A Boolean circuit with input bits is a directed acyclic graph in which every node (usually called ''gates'' in this context) is either an input node of in-degree 0 labeled by one of the input bits, an AND gate, an OR gate, or a NOT gate. One of these gates is designated as the output gate. Such a circuit naturally computes a function of its inputs. The size of a circuit is the number of gates it contains and its depth is the maximal length of a path from an input gate to the output gate. There are two major notions of circuit complexity (these are outlined in Sipser (1997)〔Sipser, M. (1997). 'Introduction to the theory of computation.' Boston: PWS Pub. Co.〕). The circuit-size complexity of a Boolean function is the minimal size of any circuit computing . The circuit-depth complexity of a Boolean function is the minimal depth of any circuit computing . These notions generalize when one considers the circuit complexity of a recursive language: A formal language may contain strings with many different bit lengths. Boolean circuits, however, only allow a fixed number of input bits. Thus no single Boolean circuit is capable of deciding such a language. To account for this possibility, one considers families of circuits where each accepts inputs of size . Each circuit family will naturally generate a recursive language by outputting when a string is a member of the family, and otherwise. We say that a family of circuits is size minimal if there is no other family that decides on inputs of any size, , with a circuit of smaller size than (respectively for depth minimal families). Hence, the circuit-size complexity of a recursive language is defined as the function , that relates a bit length of an input, , to the circuit-size complexity of a minimal circuit that decides whether inputs of that length are in . The circuit-depth complexity is defined similarly. Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0 and NC. ==Uniformity== Boolean circuits are one of the prime examples of so-called non-uniform models of computation in the sense that inputs of different lengths are processed by different circuits, in contrast with uniform models such as Turing machines where the same computational device is used for all possible input lengths. An individual computational problem is thus associated with a particular ''family'' of Boolean circuits where each is the circuit handling inputs of ''n'' bits. A ''uniformity'' condition is often imposed on these families, requiring the existence of some resource-bounded Turing machine which, on input ''n'', produces a description of the individual circuit . When this Turing machine has a running time polynomial in ''n'', the circuit family is said to be P-uniform. The stricter requirement of DLOGTIME-uniformity is of particular interest in the study of shallow-depth circuit-classes such as AC0 or TC0. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Circuit complexity」の詳細全文を読む スポンサード リンク
|